1. Field of the Invention
The present invention relates to a method of generating a node identifier in a tree structure. More particularly, the present invention relates to a method of generating a node identifier to easily ascertain a location of a node in a k-nary tree structure.
2. Description of Related Art
Along with the development of wireless communication and digital broadcasting technologies, service providers offer users a variety of contents via wire or wireless networks. Service providers having a number of users, manage service user groups by using a tree structure for reliable service. Under an environment where group members are frequently changed and are managed using a tree structure, the tree structure may quickly become unbalanced due to the frequent entry and withdrawal of a group member. Accordingly, each group member corresponding to a leaf node in the tree structure has a different depth value. Therefore, in an unbalanced tree structure, the depth value of each leaf node is different, as opposed to a balanced tree structure where all leaf nodes have an identical depth value. Accordingly, depth information of group members in an unbalanced tree structure is required to be additionally provided. Also, a method of ascertaining the depths of leaf nodes and intermediate nodes, and a path from a root node to a target node, is required to be provided so as to easily ascertain a location of the target node and efficiently use the method when updating changed information of group members.
FIG. 1 is a diagram illustrating a method of generating a node identifier in a conventional binary tree structure.
In FIG. 1, the binary tree includes a root node 100, left and right nodes of a first level 102 and 104, nodes of a second level 106, 108, 110, and 112, nodes of a third level, and nodes of a fourth level. In this instance, the root node 100 branches off to the nodes of the first level 102 and 104, and each of the left and right nodes of the first level 102 and 104 branches off to the nodes of the second level 106, 108, 110, and 112. Also, each of the nodes of the second level 106, 108, 110, and 112 branches off to the nodes of the third level, and the nodes of the third level branches off to the nodes of the fourth level.
According to the method of generating a node identifier in a conventional binary tree structure, a node identifier of the root node 100 is generated as 0, a node identifier of the left node 102 of the first level is generated as 1, and a node identifier of the right node 104 of the first level is generated as 2. Node identifiers of the nodes of the second level 106, 108, 110, and 112 are sequentially generated from left to right as 3, 4, 5, and 6, in ascending order, respectively. Similarly, node identifiers of the nodes of the third level and fourth level are sequentially generated.
According to the method of generating a node identifier in a conventional binary tree structure, when members corresponding to each node are repeatedly added and deleted as time passes, an unbalanced tree structure such as an example tree structure illustrated in FIG. 2 is generated. According to the conventional art, in the unbalanced tree structure as illustrated in FIG. 2, a fixed rule for indicating a location and depth information of each node may not be acquired, and thus a member management and tree structure update may not be efficiently performed. Accordingly, there is a need for a method of generating a node identifier to easily ascertain a location of a node in a tree structure.